#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <fstream>
#include <set>
#include "tree.h"

using namespace std;

class inOrderIterator
{
public:
    inOrderIterator(Tree *root):cur(root) 
    {
	while(root) {
	    myStack.push(root);
	    root = root->left;
	}
    }

    bool hasNext() { return !myStack.empty();}

    int next() 
    {
	Tree *top = myStack.top();
	myStack.pop();
	cur = top->right;
	while(cur) {
	    myStack.push(cur);
	    cur = cur->left;
	}
	return top->data;
    }
    int get() {
        return myStack.top()->data;
    }
private:
    stack<Tree *> myStack;
    Tree *cur;
};

void traverseTree(Tree *root, Tree *root2)
{
    inOrderIterator iter1(root), iter2(root2);
    int first, second;
    int last = -1;
    while(iter1.hasNext() && iter2.hasNext()) {
        if (iter1.get() <= iter2.get()) {
	    cout << iter1.next() << "";
	    getchar();
	} else {
	    cout << iter2.next() << " ";
	    getchar();
	}
    }
    while (iter1.hasNext()) {
	cout << iter1.next() << " ";
	    getchar();
    }

    while (iter2.hasNext())  {
	cout << iter2.next() << " ";
	    getchar();
    }
}


int main(int argc, char **argv)
{
    int input[] = {21,7,5,6,3,2,1,4,6,11,35,56};
    int input2[] = {6,23,43,54,12,54,8,10,11,35,56};
    //int input[] = {7};
    Tree *root = NULL, *root2 = NULL;
    int result;

    for (int i = 0; i < sizeof(input)/sizeof(int); i++) {
        TreeInsert(root, input[i]);
    }

    for (int i = 0; i < sizeof(input2)/sizeof(int); i++) {
        TreeInsert(root2, input2[i]);
    }
    print_ascii_tree(root);
    print_ascii_tree(root2);
    traverseTree(root, root2);
}
